import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/9 9:28
 * @description 深度优先，栈
 */
public class Solution3 {
    public static void main(String[] args) {

    }
    class Node{
        TreeNode node;
        int depth;
        Node(TreeNode node, int n) {
            this.node = node;
            this.depth = n;
        }
    }
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode t = new TreeNode(val);
            t.left = root;
            return t;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(new Node(root, 1));
        while (!stack.isEmpty()) {
            Node n = stack.pop();
            if (n.node == null) {
                continue;
            }
            if (n.depth == depth - 1) {
                TreeNode node = n.node.left;
                n.node.left = new TreeNode(val);
                n.node.left.left = node;
                node = n.node.right;
                n.node.right = new TreeNode(val);
                n.node.right.right = node;
            }else {
                stack.push(new Node(n.node.left, n.depth + 1));
                stack.push(new Node(n.node.right, n.depth + 1));
            }
        }
        return root;
    }
}
